import java.util.*;

/**
 * Created by L.jp
 * Description:给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 *输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
 *  请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

 * User: 86189
 * Date: 2021-11-07
 * Time: 0:08
 */
//求最长子串问题，用滑动窗口的方法，定义两个左指针和右指针，让right-left+1就是最长的长度，不重复子串用set解决
    //所以此题用滑动窗口+set解决问题
public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s){
        /*
        int res = 0;//存储最长长度
        Set<Character> set = new HashSet<>();//存储不重复的元素
        for(int left = 0, right = 0;right < s.length(); right++) {//定义左指针和右指针
            char c = s.charAt(right);
            while(set.contains(c)) {
                //当有多个重复字母时，需要让左指针一直向右边走，直到set不包含重复的字符
                set.remove(s.charAt(left++));
            }
            set.add(c);//不包含重复的，就添加元素
            res = Math.max(res, right - left + 1);//没添加一个不重复的元素就要更新一次最长长度
        }
        return res;

         */
        //用链表实现队列，队列是先进先出的,用队列解决不重复的最长子串问题好像更好理解，有多次重复的就利用循环弹出队头元素，最后转化为求队列的长度
        Queue<Character> queue = new LinkedList<>();
        int res = 0;
        for (char c : s.toCharArray()) {
            while (queue.contains(c)) {
                //如果有重复的，队头出队
                queue.poll();
            }
            //添加到队尾
            queue.add(c);
            res = Math.max(res, queue.size());
        }
        return res;
    }

    public static void main(String[] args) {
        String str="pwwkew";
        System.out.println(lengthOfLongestSubstring(str));
        Set<String> set=new HashSet<>();


    }
}
